//
// Created by yangchao on 2022/6/8.
// 134. 加油站: https://leetcode.cn/problems/gas-station/
//

#include <vector>
using namespace std;

//什么思想？ 数学证明？
class CanCompleteCircuit {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int i = 0;

        // 从头到尾遍历每个加油站，并且检查以该加油站为起点，能否行驶一周
        while (i < n) {
            int sumGas = 0, sumCost = 0;
            int cnt = 0;                        // 记录能走过几个站点
            while (cnt < n) {
                int j = (i + cnt) % n;          // 加油站是环形的
                sumGas += gas[j];
                sumCost += cost[j];
                if (sumCost > sumGas) break;    // 如果这个站点发现油不够了
                cnt++;  // 这个站点满足情况
            }
            if (cnt == n) {     // 如果能环绕一圈
                return i;
            } else{
                i = i + cnt + 1;        // 不行的话 从下一个站点开始 检查
            }
        }
        return -1;
    }
};

